// https://www.lintcode.com/problem/kth-largest-element/

public class Solution {
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int n, int[] nums) {
        // write your code here
        int start = 0, end = nums.length;
        while (true) {
            int[] ret = partition(nums, start, end);
            if (ret[1] != n) {
                if (ret[1] > n) {
                    start = nums.length - ret[1] + 1;
                } else {
                    end = nums.length - ret[1];
                }
            } else {
                return ret[0];
            }
        }
    }

    protected int[] partition(int[] nums, int start, int end) {
        int[] ret = new int[]{nums[start], start};
        for (int i = start + 1; i < end; ++i) {
            if (nums[i] < ret[0]) {
                ++ret[1]; // 记录比ret[0]小的元素个数
                if (ret[1] != i) { // 把比ret[0]小的元素都换到前面去
                    int tmp = nums[i];
                    nums[i] = nums[ret[1]];
                    nums[ret[1]] = tmp;
                }
            }
        }
        int tmp = nums[start];
        nums[start] = nums[ret[1]];
        nums[ret[1]] = tmp;
        ret[1] = nums.length - ret[1];
        return ret;
    }
}